package com.leetcode.partition7;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2021/9/20 9:11
 */
public class LC673最长递增子序列的个数 {

    private static int maxLength = 1;

    public static int findNumberOfLIS(int[] nums) {
//        List<List<Integer>> sequences = new ArrayList<>();
//        for (int i = 0; i < nums.length; i++) {
//            memoization(sequences, new ArrayList<>(), nums, i, new HashSet<>());
//        }
//        return sequences.size();
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 2, 2, 2};
//        int[] nums = {2, 2, 2, 2, 2};
//        int[] nums = {1, 2, 4, 3, 5, 4, 7, 2};
//        int[] nums = new int[1000];
//        Random random = new Random();
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = random.nextInt(100);
//        }
        System.out.println(findNumberOfLIS(nums));
    }

    private static int dynamicProgramming(int[] nums) {
        if (nums.length <= 1) return nums.length;
        //dp[i]表示nums[0, i]最长递增子序列的长度   count[i]表示nums[0, i]最长递增子序列的个数
        int[] dp = new int[nums.length], count = new int[nums.length];
        //初始化
        for (int i = 0; i < nums.length; i++) dp[i] = count[i] = 1;
        int max = 1, answer = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        //当前nums[j]能和dp[i]组成一个更长的递增子序列，重置计数器
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        //当前nums[j]能组成和dp[i]一样长度的最长递增子序列，累加就行
                        count[i] += count[j];
                    }
                    max = Math.max(max, dp[i]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(count));
        for (int i = 0; i < nums.length; i++) {
            if (dp[i] == max) {
                answer += count[i];
            }
        }
        return answer;
    }

    private static void memoization(List<List<Integer>> sequences, List<Integer> path, int[] nums, int startIndex, Set<List<Integer>> memo) {
        if (nums.length - startIndex + 2 + path.size() < maxLength) return;
        if (memo.contains(path)) return;

        if (startIndex == nums.length) {
            maxLength = Math.max(maxLength, path.size());
            if (path.size() < maxLength) return;
            sequences.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (path.size() > 0 && path.get(path.size() - 1) >= nums[i]) continue;

            path.add(nums[i]);
            memoization(sequences, path, nums, i + 1, memo);
            path.remove(path.size() - 1);
            memo.add(path);
        }
    }
}
